class Solution(object):
    def cheapestJump(self, coins, maxJump):
        """
        :type coins: List[int]
        :type maxJump: int
        :rtype: List[int]
        """
        n = len(coins)
        DP = [-1] * n
        DP[0] = 0
        path = [set() for _ in range(n)]
        for i in range(1, n):
            if coins[i] == -1:
                continue
            min_value = float('inf')
            for k in range(max(0, i - maxJump), i):
                if DP[k] != -1:
                    if DP[k] + coins[k] < min_value:
                        min_value = DP[k] + coins[k]
                        DP[i] = min_value
                        path[i] = {k}
                    else:
                        if DP[k] + coins[k] == min_value:
                            path[i].add(k)
        if DP[-1] == -1:
            return []
        now_out = []
        self.result = None

        def search(i):
            if i == 0:
                now_out.append(i + 1)
                now_result = now_out.copy()
                now_result.reverse()
                if not self.result:
                    self.result = tuple(now_result)
                else:
                    self.result = min(self.result, tuple(now_result))
                now_out.pop()
            else:
                now_out.append(i + 1)
                for item in path[i]:
                    search(item)
                now_out.pop()

        search(n - 1)
        return list(self.result)

data = Solution()
coins = [1,2,4,-1,2]
maxJump = 1
print(data.cheapestJump(coins, maxJump))
